#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<ll,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int MAXN = 1e5+10;
const int MAXE = 2e6+10;

struct node{int id,v,w;};
vector <node> G[MAXN];
vector <node> T[MAXE];
vector <int> to[MAXN],ot[MAXN];
bool operator < (node x,node y){return x.w < y.w;}

int cnt,n,m,ec,id[MAXN<<1],x,y,z;
ll dis[MAXE+MAXN];bool v[MAXE];
void link(int x,int y,int w){ec++;G[x].pb((node){ec,y,w});G[y].pb((node){ec,x,w});}
void llink(int x,int y,int w){T[x].pb((node){0,y,w});}

void dijk(int s){
	memset(dis,0x3f,(cnt+20)<<3);
	dis[s] = 0; priority_queue<pii> q; q.push(pii(0,s));
	while(q.size()){
		int x = q.top().se;q.pop(); if(v[x]) continue; v[x] = 1;
		for(auto d : T[x]){
			int y = d.v,w = d.w;
			if(dis[x] + w < dis[y]){
				dis[y] = dis[x] + w;
				q.push(pii(-dis[y],y));
			}
		}
	}
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in;
	for(int i = 1;i <= m;i++) x = in,y = in,z = in,link(x,y,z);
	link(0,1,0); link(n,n+1,0);
	for(int x = 0;x <= n+1;x++){
		sort(G[x].begin(),G[x].end());
		to[x].resize(G[x].size()); ot[x].resize(G[x].size());
		for(int j = 0;j < G[x].size();j++){
			if(!id[G[x][j].id]) id[G[x][j].id] = ++cnt;
			to[x][j] = ++cnt; ot[x][j] = ++cnt;
			llink(to[x][j],id[G[x][j].id],0); if(j) llink(to[x][j],to[x][j-1],0);
			llink(id[G[x][j].id],ot[x][j],0); if(j) llink(ot[x][j-1],ot[x][j],0);
			llink(id[G[x][j].id],to[x][j],G[x][j].w); llink(ot[x][j],id[G[x][j].id],G[x][j].w);
		}
	}dijk(id[G[0][0].id]);
	printf("%lld\n",dis[id[G[n+1][0].id]]);
	return 0;
}

